package leetcode.hot100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Deque;

public class Solution239 {

    public static void main(String[] args) {

        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] res = new Solution239().maxSlidingWindow(nums,k);
        res = new Solution239().maxSlidingWindow1(nums,k);
//        System.out.println(Arrays.asList(res));

    }

    public int[] maxSlidingWindow1(int[] nums, int k) {
        long tic = System.currentTimeMillis();

        //结果集
        int len = nums.length;
        int[] res = new int[len-k+1];
        //单调队列，每次入队时把前面小的元素清除完，保持队列单减不增
        Deque<Integer> deque = new LinkedList<>();
        //先将前[0,k-1]个元素入队
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty()&&deque.peekLast()<nums[i]) deque.pollLast();
            deque.offerLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        //将[k,n-1]元素入队
        for (int i = k; i < len; i++) {
            while (!deque.isEmpty()&&deque.peekLast()<nums[i]) deque.pollLast();
            deque.offerLast(nums[i]);
            //判断队首是不是被滑掉的元素
            if(deque.peekFirst()==nums[i-k]) deque.pollFirst();
            res[i+1-k] = deque.peekFirst();
        }

        System.out.println("Dequeue:"+(System.currentTimeMillis()-tic));
        return res;
    }
    
    public int[] maxSlidingWindow(int[] nums, int k) {
        long tic = System.currentTimeMillis();
        //分组前后缀
        int len = nums.length;
        int[] prefix = new int[len], suffix = new int[len], res = new int[len-k+1];
        //以长度k分组，记录每组以i结尾的最大值
        for (int i = 0; i < len; i++) {
            if(i%k==0){
                prefix[i] = nums[i];
            }else {
                prefix[i] = Math.max(prefix[i-1],nums[i]);
            }
        }
        //记录每组以i开头的最大值
        int start = len-1;
        if(len%k!=0){
            suffix[len-1] = nums[len-1];
            start = len-2;
        }
        for (int i = start; i > -1; i--) {
            if((i+1)%k==0){ //分组末尾
                suffix[i] = nums[i];
            }else {
                suffix[i] = Math.max(suffix[i+1],nums[i]);
            }
        }
        //res[i] = max(suffix[i],prefix[i+k-1])
        for (int i = 0; i < len-k+1; i++) {
            res[i] = Math.max(suffix[i],prefix[i+k-1]);
        }

        System.out.println("Suffix:"+(System.currentTimeMillis()-tic));
        return res;
    }
}
